/* crypto/ec/ec2_lopezdahab.c */
/*-
 * Copyright (c) 2012 Politecnico di Torino, Italy.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 *
 * Written by Simone Basso and Matteo Avalle.
 */

/*
 * GF(2m) operations in Lopez-Dahab coordinates.
 */

#include <stdio.h>
#include <string.h>

#include <openssl/err.h>
#include "ec_lcl.h"

#ifndef OPENSSL_NO_EC2M

#ifdef OPENSSL_FIPS
#include <openssl/fips.h>
#endif

/*
 * Lopez-Dahab context.  Contains the bignum context and the group,
 * plus a number of temporary bignums for computation.  It should be
 * created on the stack and initialized with lopezdahab_init before
 * starting the multiplication.  It must be cleared in any case with
 * lopezdahab_finish just before returning to the caller.
 */

/*
 * Definitions autogenerated by: ./tools/ec2_lopezdahab.py
 */

struct lopezdahab {
	BN_CTX		*ctx;
	const EC_GROUP	*group;
	BIGNUM		regs[37];
	unsigned int	flags;
};

#define		ld_A	regs[0]
#define		ld_B	regs[1]
#define		ld_C	regs[2]
#define		ld_D	regs[3]
#define		ld_E	regs[4]
#define		ld_F	regs[5]
#define		ld_G	regs[6]
#define		ld_H	regs[7]
#define		ld_I	regs[8]
#define		ld_J	regs[9]
#define		ld_X1	regs[10]
#define		ld_X2	regs[11]
#define		ld_X3	regs[12]
#define		ld_Y1	regs[13]
#define		ld_Y2	regs[14]
#define		ld_Y3	regs[15]
#define		ld_Z1	regs[16]
#define		ld_Z2	regs[17]
#define		ld_Z3	regs[18]
#define		ld_a2	regs[19]
#define		ld_a6	regs[20]
#define		ld_t0	regs[21]
#define		ld_t1	regs[22]
#define		ld_t10	regs[23]
#define		ld_t11	regs[24]
#define		ld_t12	regs[25]
#define		ld_t13	regs[26]
#define		ld_t14	regs[27]
#define		ld_t15	regs[28]
#define		ld_t2	regs[29]
#define		ld_t3	regs[30]
#define		ld_t4	regs[31]
#define		ld_t5	regs[32]
#define		ld_t6	regs[33]
#define		ld_t7	regs[34]
#define		ld_t8	regs[35]
#define		ld_t9	regs[36]

/* End autogenerated definitions */

#define			LOPEZDAHAB_F_CTX (1<<0)		/* must free() ctx */

/* Just in case it was not defined */
#ifndef nitems
#  define nitems(_x)	(sizeof((_x)) / sizeof((_x)[0]))
#endif

/* Initialize the Lopez-Dahab context */
static int
lopezdahab_init(struct lopezdahab *ld, BN_CTX *ctx, const EC_GROUP *group)
{
	int	i;

	memset(ld, 0, sizeof (*ld));
	if (ctx == NULL) {
		ld->flags |= LOPEZDAHAB_F_CTX;
		ctx = BN_CTX_new();
		if (ctx == NULL)
			return (0);
	}
	ld->ctx = ctx;
	ld->group = group;
	BN_CTX_start(ld->ctx);
	for (i = 0; i < nitems(ld->regs); ++i)
		BN_init(&ld->regs[i]);

	/* copy curve parameters */
	if (!BN_copy(&ld->ld_a2, &group->a))
		return (0);
	if (!BN_copy(&ld->ld_a6, &group->b))
		return (0);

	return (1);
}

/* Cleanup the Lopez-Dahab context */
static void
lopezdahab_finish(struct lopezdahab *ld)
{
	int	i;

	for (i = 0; i < nitems(ld->regs); ++i)
		BN_free(&ld->regs[i]);
	if (ld->ctx != NULL) {
		BN_CTX_end(ld->ctx);
		if (ld->flags & LOPEZDAHAB_F_CTX)
			BN_CTX_free(ld->ctx);
	}
}

/*
 * Low-level operations implementation.
 * Note that the macros assume that a struct lopezdahab named
 * ``ld`` is declared in the current scope.
 * The autogenerated code from the formulae (below) is not
 * OpenSSL specific, so we can change the macro in future
 * to point to more efficient code, e.g. something like the
 * code for nistp224 by Emilia Kasper.
 */

#define LOPEZDAHAB_SUM(res, op1, op2)					\
	if (!BN_GF2m_add(res, op1, op2))				\
		return (0)

#define LOPEZDAHAB_MUL(res, op1, op2)					\
	if (!BN_GF2m_mod_mul_arr(res, op1, op2, ld->group->poly,	\
	    ld->ctx))							\
		return (0)

#define LOPEZDAHAB_SQUARE(res, op1)					\
	if (!BN_GF2m_mod_sqr_arr(res, op1, ld->group->poly,		\
	    ld->ctx))							\
		return (0)

#define LOPEZDAHAB_INV(res, op1)					\
	if (!BN_GF2m_mod_inv(res, op1, &ld->group->field, ld->ctx))	\
		return (0)

/*
 * Code autogenerated by: ./tools/ec2_lopezdahab.py
 */

/* dbl-2005-l.op3 (http://www.hyperelliptic.org/EFD/) */
static int
lopezdahab_dbl_2005_l(struct lopezdahab *ld)
{
	LOPEZDAHAB_MUL(&ld->ld_A, &ld->ld_X1, &ld->ld_Z1);
	LOPEZDAHAB_SQUARE(&ld->ld_B, &ld->ld_X1);
	LOPEZDAHAB_SUM(&ld->ld_C, &ld->ld_B, &ld->ld_Y1);
	LOPEZDAHAB_MUL(&ld->ld_D, &ld->ld_A, &ld->ld_C);
	LOPEZDAHAB_SQUARE(&ld->ld_Z3, &ld->ld_A);
	LOPEZDAHAB_SQUARE(&ld->ld_t0, &ld->ld_C);
	LOPEZDAHAB_MUL(&ld->ld_t1, &ld->ld_a2, &ld->ld_Z3);
	LOPEZDAHAB_SUM(&ld->ld_t2, &ld->ld_t0, &ld->ld_D);
	LOPEZDAHAB_SUM(&ld->ld_X3, &ld->ld_t2, &ld->ld_t1);
	LOPEZDAHAB_SUM(&ld->ld_t3, &ld->ld_Z3, &ld->ld_D);
	LOPEZDAHAB_SQUARE(&ld->ld_t4, &ld->ld_B);
	LOPEZDAHAB_MUL(&ld->ld_t5, &ld->ld_t4, &ld->ld_Z3);
	LOPEZDAHAB_MUL(&ld->ld_t6, &ld->ld_t3, &ld->ld_X3);
	LOPEZDAHAB_SUM(&ld->ld_Y3, &ld->ld_t6, &ld->ld_t5);

	return (1);
}

/* add-2005-dl.op3 (http://www.hyperelliptic.org/EFD/) */
static int
lopezdahab_add_2005_dl(struct lopezdahab *ld)
{
	LOPEZDAHAB_MUL(&ld->ld_A, &ld->ld_X1, &ld->ld_Z2);
	LOPEZDAHAB_MUL(&ld->ld_B, &ld->ld_X2, &ld->ld_Z1);
	LOPEZDAHAB_SQUARE(&ld->ld_C, &ld->ld_A);
	LOPEZDAHAB_SQUARE(&ld->ld_D, &ld->ld_B);
	LOPEZDAHAB_SUM(&ld->ld_E, &ld->ld_A, &ld->ld_B);
	LOPEZDAHAB_SUM(&ld->ld_F, &ld->ld_C, &ld->ld_D);
	LOPEZDAHAB_SQUARE(&ld->ld_t0, &ld->ld_Z2);
	LOPEZDAHAB_MUL(&ld->ld_G, &ld->ld_Y1, &ld->ld_t0);
	LOPEZDAHAB_SQUARE(&ld->ld_t1, &ld->ld_Z1);
	LOPEZDAHAB_MUL(&ld->ld_H, &ld->ld_Y2, &ld->ld_t1);
	LOPEZDAHAB_SUM(&ld->ld_I, &ld->ld_G, &ld->ld_H);
	LOPEZDAHAB_MUL(&ld->ld_J, &ld->ld_I, &ld->ld_E);
	LOPEZDAHAB_MUL(&ld->ld_t2, &ld->ld_Z1, &ld->ld_Z2);
	LOPEZDAHAB_MUL(&ld->ld_Z3, &ld->ld_F, &ld->ld_t2);
	LOPEZDAHAB_SUM(&ld->ld_t3, &ld->ld_H, &ld->ld_D);
	LOPEZDAHAB_SUM(&ld->ld_t4, &ld->ld_C, &ld->ld_G);
	LOPEZDAHAB_MUL(&ld->ld_t5, &ld->ld_B, &ld->ld_t4);
	LOPEZDAHAB_MUL(&ld->ld_t6, &ld->ld_A, &ld->ld_t3);
	LOPEZDAHAB_SUM(&ld->ld_X3, &ld->ld_t6, &ld->ld_t5);
	LOPEZDAHAB_MUL(&ld->ld_t7, &ld->ld_F, &ld->ld_G);
	LOPEZDAHAB_MUL(&ld->ld_t8, &ld->ld_A, &ld->ld_J);
	LOPEZDAHAB_SUM(&ld->ld_t9, &ld->ld_t8, &ld->ld_t7);
	LOPEZDAHAB_SUM(&ld->ld_t10, &ld->ld_J, &ld->ld_Z3);
	LOPEZDAHAB_MUL(&ld->ld_t11, &ld->ld_t10, &ld->ld_X3);
	LOPEZDAHAB_MUL(&ld->ld_t12, &ld->ld_t9, &ld->ld_F);
	LOPEZDAHAB_SUM(&ld->ld_Y3, &ld->ld_t12, &ld->ld_t11);

	return (1);
}

/* End autogenerated code */

/*
 * Load and store
 */

/* Load a point and optionally convert it to Lopez-Dahab coordinates */
static int
lopezdahab_load(BIGNUM *X3, BIGNUM *Y3, BIGNUM *Z3, const BIGNUM *X1,
    const BIGNUM *Y1, const BIGNUM *Z1, int convert)
{
	if (!convert) {
		/* Already in Lopez-Dahab coordinates */
		if (!BN_copy(X3, X1))
			return (0);
		if (!BN_copy(Y3, Y1))
			return (0);
		if (!BN_copy(Z3, Z1))
			return (0);
	} else if (BN_is_zero(Z1)) {
		/*
		 * When the input point is the point at the
		 * infinity (identified by the flag Z=0), we
		 * are very strict and the output point is
		 * (1,0,0), which is the exact representation
		 * of the point at infinity in Lopez-Dahab
		 * coordinates.
		 */
		if (!BN_set_word(X3, 1))
			return (0);
		if (!BN_set_word(Y3, 0))
			return (0);
		if (!BN_set_word(Z3, 0))
			return (0);
	} else {
		if (!BN_copy(X3, X1))
			return (0);
		if (!BN_copy(Y3, Y1))
			return (0);
		/*
		 * Here we assume that the input point is
		 * affine and we take the liberty of setting
		 * Z3 to 1 without bothering to check the
		 * exact value of Z1, i.e. for us Z1 is just
		 * a boolean flag.
		 */
		if (!BN_set_word(Z3, 1))
			return (0);
	}

	return (1);
}

/* Get P1 coordinates from (X,Y,Z) */
static int
lopezdahab_load_P1(struct lopezdahab *ld, const BIGNUM *X, const BIGNUM *Y,
    const BIGNUM *Z, int convert)
{
	return (lopezdahab_load(&ld->ld_X1, &ld->ld_Y1, &ld->ld_Z1,
	    X, Y, Z, convert));
}

/* Get P2 coordinates from (X,Y,Z) */
static int
lopezdahab_load_P2(struct lopezdahab *ld, const BIGNUM *X,
    const BIGNUM *Y, const BIGNUM *Z, int convert)
{
	return (lopezdahab_load(&ld->ld_X2, &ld->ld_Y2, &ld->ld_Z2,
	    X, Y, Z, convert));
}

/* Store a point and optionally convert it from Lopez-Dahab coordinates */
static int
lopezdahab_store(struct lopezdahab *ld, BIGNUM *X3, BIGNUM *Y3, BIGNUM *Z3,
    const BIGNUM *X1, const BIGNUM *Y1, const BIGNUM *Z1, int convert)
{
	if (!convert) {
		/* Stay in Lopez-Dahab coordinates */
		if (!BN_copy(X3, X1))
			return (0);
		if (!BN_copy(Y3, Y1))
			return (0);
		if (!BN_copy(Z3, Z1))
			return (0);
	} else if (BN_is_zero(Z1)) {
		/*
		 * When the input point is the point at the
		 * infinity (identified by Z=0 in Lopez-
		 * Dahab coordinates), the output point is
		 * (1,0,0), which is a valid representation
		 * of the point at infinity in affine coordinates
		 * (any point with Z=0 will do).
		 */
		if (!BN_set_word(X3, 1))
			return (0);
		if (!BN_set_word(Y3, 0))
			return (0);
		if (!BN_set_word(Z3, 0))
			return (0);
	} else {
		/*
		 * The point (X, Y, Z) in lopezdahab coordinates is
		 * converted to (X/Z, Y/Z^2) in affine coordinates.
		 */
		LOPEZDAHAB_INV(&ld->ld_t0, Z1);
		LOPEZDAHAB_MUL(X3, X1, &ld->ld_t0);
		LOPEZDAHAB_SQUARE(&ld->ld_t0, &ld->ld_t0);
		LOPEZDAHAB_MUL(Y3, Y1, &ld->ld_t0);
		/*
		 * Reset Z to 1
		 */
		if (!BN_set_word(Z3, 1))
			return (0);
	}

	return (1);
}

/* Save P3 coordinates into (X,Y,Z) */
static int
lopezdahab_store_P3(struct lopezdahab *ld, BIGNUM *X, BIGNUM *Y, BIGNUM *Z,
    int convert)
{
	return (lopezdahab_store(ld, X, Y, Z, &ld->ld_X3, &ld->ld_Y3,
	    &ld->ld_Z3, convert));
}

/*
 * Add and double
 */

/* Internal implementation of DBL in Lopez-Dahab coordinates */
static int
lopezdahab_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
    BN_CTX *ctx, int convert)
{
	struct	lopezdahab ld;
	int	result = 0;

	/*
	 * When the input is already in Lopez-Dahab coordinates
	 * don't bother with checking for corner cases because we
	 * assume that we're invoked as a building block for the
	 * MUL and that the caller has provided a "good" point,
	 * so we'll never get to the point at infinity.
	 * NB: The double of the point at infinity is the point at
	 * infinity.
	 */
	if (convert && EC_POINT_is_at_infinity(group, a))
		return (EC_POINT_set_to_infinity(group, r));

	if (!lopezdahab_init(&ld, ctx, group))
		goto end;
	if (!lopezdahab_load_P1(&ld, &a->X, &a->Y, &a->Z, convert))
		goto end;
	if (!lopezdahab_dbl_2005_l(&ld))
		goto end;
	if (!lopezdahab_store_P3(&ld, &r->X, &r->Y, &r->Z, convert))
		goto end;
	result = 1;

end:	lopezdahab_finish(&ld);
	return (result);
}

/* Internal implementation of ADD in Lopez-Dahab coordinates */
static int
lopezdahab_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
    const EC_POINT *b, BN_CTX *ctx, int convert)
{
	struct	lopezdahab ld;
	int	result = 0;

	/*
	 * When the input is already in Lopez-Dahab coordinates
	 * don't bother with checking for corner cases because we
	 * assume that we're invoked as a building block for the
	 * MUL and that the caller has provided a "good" point,
	 * so we'll never get to the point at infinity.
	 */
	if (convert) {
		/*
		 * When one of the two points is at infinity
		 * the result is the other point.
		 */
		if (EC_POINT_is_at_infinity(group, a))
			return (EC_POINT_copy(r, b));
		if (EC_POINT_is_at_infinity(group, b))
			return (EC_POINT_copy(r, a));
		/*
		 * When the two points are one the inverse
		 * of the other the result is our friend the
		 * point at infinity.
		 * When the two points are equal the explicit
		 * formula for ADD does not work and we need
		 * instead to use the DBL formula.
		 */
		if (BN_cmp(&a->X, &b->X) == 0) {
			if (BN_cmp(&a->Y, &b->Y) != 0)
				return (EC_POINT_set_to_infinity(group, r));
			else
				return (lopezdahab_dbl(group, r, a,
				    ctx, convert));
		}
	}

	if (!lopezdahab_init(&ld, ctx, group))
		goto end;
	if (!lopezdahab_load_P1(&ld, &a->X, &a->Y, &a->Z, convert))
		goto end;
	if (!lopezdahab_load_P2(&ld, &b->X, &b->Y, &b->Z, convert))
		goto end;
	if (!lopezdahab_add_2005_dl(&ld))
		goto end;
	if (!lopezdahab_store_P3(&ld, &r->X, &r->Y, &r->Z, convert))
		goto end;
	result = 1;

end:	lopezdahab_finish(&ld);
	return (result);
}

/*
 * For testing
 */

/* Perform affine ADD in Lopez-Dahab coordinates */
int
ec_GF2m_lopezdahab_add(const EC_GROUP *group, EC_POINT *r,
    const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
{
	return (lopezdahab_add(group, r, a, b, ctx, 1));
}

/* Perform affine DBL in Lopez-Dahab coordinates */
int
ec_GF2m_lopezdahab_dbl(const EC_GROUP *group, EC_POINT *r,
    const EC_POINT *a, BN_CTX *ctx)
{
	return (lopezdahab_dbl(group, r, a, ctx, 1));
}

/* Perform Lopez-Dahab ADD in Lopez-Dahab coordinates */
int
__ec_GF2m_lopezdahab_add(const EC_GROUP *group, EC_POINT *r,
    const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
{
	return (lopezdahab_add(group, r, a, b, ctx, 0));
}

/* Perform Lopez-Dahab DBL in Lopez-Dahab coordinates */
int
__ec_GF2m_lopezdahab_dbl(const EC_GROUP *group, EC_POINT *r,
    const EC_POINT *a, BN_CTX *ctx)
{
	return (lopezdahab_dbl(group, r, a, ctx, 0));
}

/*
 * TODO Still I don't know whether we can use the generic wNAF
 * or we need to write our custom wNAF loop.
 */

#endif /* !OPENSSL_NO_EC2M */
